#include <stdio.h>
#include <stdlib.h>

#define MAX 32767

typedef struct Graph{
    char *vexs;
    int **arcs;
    int vexNum;
    int arcNum;
} Graph;


Graph *initGraph(int vexNum) //顶点数
{
    Graph *G = (Graph *)malloc(sizeof(Graph));
    G->arcs = (int **)malloc(sizeof(int *) * vexNum);
    G->vexs = (char *)malloc(sizeof(char) * vexNum);
    for (int i = 0; i < vexNum; i++) {
        G->arcs[i] = (int *)malloc(sizeof(int) * vexNum);
    }
    G->arcNum = 0;
    G->vexNum = vexNum;
    return G;
}

void createGraph(Graph *G, char *vexs, int *arcs)
{
    for (int i = 0; i < G->vexNum; i++) {
        G->vexs[i] = vexs[i];
        for (int j = 0; j < G->vexNum; j++) { //注意此时只是普通的二级指针
            G->arcs[i][j] = *(arcs + i * G->vexNum + j);
            if (G->arcs[i][j] != 0 && G->arcs[i][j] != MAX) {
                G->arcNum++;
            }
        }
    }
    G->arcNum /= 2;
}

void DFS(Graph *G, int *visited, int index) //索引第一个节点开始
{
    printf("%c ", G->vexs[index]);//访问
    visited[index] = 1;
    for (int i = 0; i < G->vexNum; i++) {
        if (G->arcs[index][i] > 0 && G->arcs[index][i] != MAX && !visited[i]) {//遍历 + 递归
            DFS(G, visited, i);
        }
    }
}

int getMin(int *d, int *s, Graph *G)
{
    int index;
    int min = MAX;
    for (int i = 0; i < G->vexNum; i++) {
        if (d[i] < min && !s[i]) {
            min = d[i];
            index = i;
        }
    }
    return index;
}

void dijkstra(Graph *G, int index)
{
    /**
     * 1. 初始化三个数组 初始化更详细的逻辑看最后
     * 2. 循环n-1次(第一个已找到) 找到d[i]最小值 更新s[i], p[i] 
     */
    int *s = (int *)malloc(sizeof(int) * G->vexNum);
    int *p = (int *)malloc(sizeof(int) * G->vexNum);
    int *d = (int *)malloc(sizeof(int) * G->vexNum);
    //1.
    for (int i = 0; i < G->vexNum; i++) {//记录最短路径是否求得
        d[i] = G->arcs[index][i];//d[i]可直接赋值
        if (i == index) {
            s[i] = 1;//自己加入
        } else {
            s[i] = 0;//除了
        }
        if (G->arcs[index][i] > 0 && G->arcs[index][i] != MAX) {
            p[i] = index; 
        } else {
            p[i] = -1;
        }
    }
    for (int i = 0; i < G->vexNum-1; i++) {
        int index;
        index =getMin(d, s, G);
        s[index] = 1;
        for (int j = 0; j < G->vexNum; j++) {
            if (!s[j] && d[index] + G->arcs[index][j] < d[j]) {//找到最短路径后就不需要调整
                d[j] = d[index] + G->arcs[index][j];
                p[j] = index;
            }
        }
    }
    for (int i = 0; i < G->vexNum; i++) 
        printf("%d %d %d\n", s[i], p[i], d[i]);
}

int main(void)
{
    Graph* G = initGraph(7);
    int* visited = (int*)malloc(sizeof(int) * G -> vexNum);
    for (int i = 0; i < G -> vexNum; i++)
        visited[i] = 0;
    int arcs[7][7] = {
            0, 12, MAX, MAX, MAX, 16, 14,
            12, 0, 10, MAX, MAX, 7, MAX,
            MAX, 10, 0, 3, 5, 6, MAX,
            MAX, MAX, 3, 0, 4, MAX, MAX,
            MAX, MAX, 5, 4, 0, 2, 8,
            16, 7, 6, MAX, 2, 0, 9,
            14, MAX, MAX, MAX, 8, 9, 0
    };
    createGraph(G, "1234567", (int*)arcs);
    DFS(G, visited, 0);
    printf("\n");
    dijkstra(G, 0);
    return 0;
}

/**
 *  for (int i = 0; i < G->vexNum; i++) {//记录最短路径是否求
        if (i == index) { //自己已求得
            s[i] = 1;
        }
        else {
            s[i] = 0; //别的
        }
    }
    for (int i = 0; i < G->vexNum; i++) {//前一个节点
        if (G->arcs[index][i] > 0 && G->arcs[index][i] != MAX) {
            p[i] = index;//和index相邻
        } else {
            p[i] = -1; //不相邻 赋值为-1
        }
    }
    for (int i = 0; i < G->vexNum; i++) {//最短路径记录
        d[i] = G->arcs[index][i];
    }

    for (int i = 0; i < G->vexNum; i++) {
        printf("%d %d %d\n", s[i], p[i], d[i]);
    }
*/